class Solution(object):
    def twoSum(self, nums, target):  # O(n^2)
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(nums)
        for i in range(length):
            for j in range(length)[i+1:]:
                if nums[i] + nums[j] == target:
                    return [i, j]
    
    # 哈希表：以空间换时间
    def twoSumFast(self, nums, target):  # O(n)
        table = dict()
        for i, n in enumerate(nums):
            if target - n in table:  # 确保已经出现过
                return [table[target - n], i]  # left index 必然小于 right index
            table[n] = i


if __name__ == '__main__':
    soln = Solution()
    print(soln.twoSumFast([2,7,11,15], 9))
    print(soln.twoSumFast([3,2,4], 6))
    print(soln.twoSumFast([3,3], 6))
